package com.fallsvc.re.javasesets.carraylistlinkedlist;

import java.util.Stack;

public class PalindromeList {

    public boolean chkPalindrome(ListNode A) {
        // write code here
        Stack<Integer> s = new Stack<>(); // 存前半部分元素
        ListNode slow = A;
        ListNode fast = A;
        while(fast != null && fast.next != null) {
            s.push(slow.val);
            slow = slow.next;
            
            fast = fast.next.next;
        }
        if(s.peek() != slow.val) {
            slow = slow.next;
        }
        while(slow != null){  // 后半部分元素进行比较
            if(slow.val != s.pop()){
                return false;
            }
            slow = slow.next;
        }
        return true;
    }


    /*
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class PalindromeList2 {
        public boolean chkPalindrome(ListNode A) {
            if(A==null){
                return true;
            }
            // write code here
            //找到中点
            ListNode fast=A;
            ListNode slow=fast;
            ListNode cur=fast;
            while(fast!=null&&fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
            }
            //翻转
            cur=slow.next;
            while(cur!=null){
                ListNode curNext=cur.next;
                cur.next=slow;
                slow=cur;
                cur=curNext;
            }
            while(A!=slow){
                if(A.val!=slow.val){
                    return false;
                }
                if(A.next!=slow){
                    return true;
                }
                A=A.next;
                slow=slow.next;
            }
            return true;
        }
    }

}